package com.example.question.dp.dp1;

public class Code05_647 {
    public static void main(String[] args) {
        Code05_647 code = new Code05_647();
        System.out.println("code.countSubstrings(\"aaa\") = " + code.countSubstrings("aaa"));
    }

    /**
     * 记忆化搜索 消除重复计算
     * 转换成字符数组之后进行操作 效率相对高一些
     */
    public int countSubstrings(String s) {
        int count = 0;
        if (s == null || s.length() == 0) {
            return count;
        }
        char[] chars = s.toCharArray();
        boolean[][] dp = new boolean[chars.length][chars.length];
        for (int col = 0; col < s.length(); col++) {
            for (int row = 0; row <= col; row++) {
                if (row == col) {
                    // 对角线的都是回文字符串
                    dp[row][col] = true;
                    count++;
                } else if (row + 1 == col) {
                    // 只有两个的时候直接比较
                    if (chars[row] == chars[col]) {
                        dp[row][col] = true;
                        count++;
                    } else {
                        dp[row][col] = false;
                    }
                } else {
                    // 超过两个的时候 先比较两端的值是否相等 再借助这个数组dp进行判断
                    dp[row][col] = chars[row] == chars[col] && dp[row + 1][col - 1];
                    if (dp[row][col]) {
                        count++;
                    }
                }
            }
        }
        return count;
    }

    /**
     * 暴力解法
     */
    public int countSubstrings1(String s) {
        int count = 0;
        if (s == null || s.length() == 0) {
            return count;
        }

        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                String str = s.substring(i, j + 1);
                if (isPalindrome(str)) {
                    count++;
                }
            }
        }
        return count;
    }

    public boolean isPalindrome(String str) {
        int left = 0;
        int right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
